package cn.walls1717.leetcode.array;

import java.util.Arrays;

/**
 * 34.在排序数组中查找元素的第一个和最后一个位置
 * 力扣地址：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 *
 * @author walls1717
 * @since 2022-04-30
 **/
public class T34 {
    public static void main(String[] args) {
        int[] nums = {};
        int target = 0;
        int[] ints = searchRange(nums, target);
        System.out.println(Arrays.toString(ints));
    }

    private static int[] searchRange(int[] nums, int target) {
        // 因为是已排序的升序数组，可以用二分法查找目标元素
        // 因为数组中有重复数据，所以二分法只会随机返回一个目标值
        int index = binarySearch(nums, target);
        System.out.println(index);
        // 设置左边界
        int left = index;
        // 右边界
        int right = index;
        // 如果二分查找返回-1了，证明数组中没有此元素，根据题意直接返回
        if (index == -1) {
            return new int[]{-1, -1};
        }
        // 第一个条件防止数组越界
        // 第二个，根据左边界判断是否还有相同的值，有相同值向左移动边界
        while (left - 1 >= 0 && nums[left - 1] == nums[index]) {
            --left;
        }
        while (right + 1 < nums.length && nums[right + 1] == nums[index]) {
            ++right;
        }
        // 返回左边界和有边界数组
        return new int[]{left, right};
    }

    /**
     * 二分查找
     * 左闭右闭 [left, right]
     *
     * @param nums 已排序的升序数组
     * @param target 目标值
     * @return 目标值下标或-1
     */
    private static int binarySearch(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        int m;
        // 数组为空，目标值小于数组第一位，目标值大于数组最后一位，直接返回-1
        if (nums.length == 0 || nums[0] > target || nums[r] < target) {
            return -1;
        }
        while (l <= r) {
            m = l + ((r - l) >> 1);
            if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }
}
